GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Turniergraph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Turniergraph</span></h1>

</header>

</div>

<p>Ein <b>Turniergraph</b> oder <b>Turnier</b> ist ein <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteter Graph</a>, in dem zwischen je zwei verschiedenen Knoten x, y genau eine Kante existiert – also entweder eine Kante von x nach y oder eine von y nach x (aber nicht beide). Außerdem darf für keinen seiner Knoten x eine Kante (x,x) existieren.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formalisierte_Definition">Formalisierte Definition</h2></div>

<p>Ein Turniergraph ist ein gerichteter Graph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"></span>, der die folgenden Bedingungen erfüllt:

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/89e1c8106b3df898a0338c2ebce32902e4941fc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.147ex; height:2.509ex;" alt="{\displaystyle x,y\in V}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\not =y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\not =y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83b07f4031454ae8fd7b2450084ac726a0330a80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.584ex; height:2.676ex;" alt="{\displaystyle x\not =y}" loading="lazy"></span> gilt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)\in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ae449747f6f0429c02e36830b8a2ff94ac3dc77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.945ex; height:2.843ex;" alt="{\displaystyle (x,y)\in E}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y,x)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y,x)\in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/882f7e261a417a9f4a6d6425b0bfee67472edf82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.945ex; height:2.843ex;" alt="{\displaystyle (y,x)\in E}" loading="lazy"></span>,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/89e1c8106b3df898a0338c2ebce32902e4941fc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.147ex; height:2.509ex;" alt="{\displaystyle x,y\in V}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\not =y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\not =y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83b07f4031454ae8fd7b2450084ac726a0330a80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.584ex; height:2.676ex;" alt="{\displaystyle x\not =y}" loading="lazy"></span> gilt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)\not \in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)\not \in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4a67dec446a4b4969b61d1c46b9222b72a58c67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.945ex; height:2.843ex;" alt="{\displaystyle (x,y)\not \in E}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y,x)\not \in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y,x)\not \in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/25ded01f9760cebeae3f075ed5292bd07775043e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.945ex; height:2.843ex;" alt="{\displaystyle (y,x)\not \in E}" loading="lazy"></span>,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa374e20b2db7f6b8caa71ff1865f7f84f215c9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.958ex; height:2.176ex;" alt="{\displaystyle x\in V}" loading="lazy"></span> gilt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,x)\not \in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,x)\not \in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ccba30b4632177a4289874ed6e3770ef15cbc579.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.119ex; height:2.843ex;" alt="{\displaystyle (x,x)\not \in E}" loading="lazy"></span>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<p>Jeder nichtleere endliche Turniergraph enthält einen <a href="Hamiltonpfad" class="mw-redirect" title="Hamiltonpfad">Hamiltonpfad</a>. (<i><a href="Satz_von_R%C3%A9dei_(Graphentheorie)" title="Satz von Rédei (Graphentheorie)">Satz von Rédei (Graphentheorie)</a></i>)

</p>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>A.A. Sapozhenko: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Tournament</cite>. In: <a href="Michiel_Hazewinkel" title="Michiel Hazewinkel">Michiel Hazewinkel</a> (Hrsg.): <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Encyclopedia_of_Mathematics" class="mw-redirect" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a></cite>. Springer-Verlag und <a href="European_Mathematical_Society" title="European Mathematical Society">EMS</a> Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, <a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php/Tournament">encyclopediaofmath.org</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Turniergraph&rft.atitle=Tournament&rft.au=A.A.+Sapozhenko&rft.btitle=Encyclopedia+of+Mathematics&rft.date=2002&rft.genre=book&rft.isbn=1556080107&rft.place=Berlin&rft.pub=Springer-Verlag+und+EMS+Press" style="display:none"> </span></li>

<li><a href="Eric_Weisstein" title="Eric Weisstein">Eric W. Weisstein</a>: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/Tournament.html"><i>Tournament</i>.</a> In: <i><a href="MathWorld" title="MathWorld">MathWorld</a></i> (englisch).</li></ul>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4473306-9">4473306-9</a></span> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-11-15" href="https://de.wikipedia.org/wiki/?title=Turniergraph&oldid=250369041">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>